package structures.binarysorttree;

import java.util.Arrays;

// 二叉排序树
public class BinarySortTreeDemo {
    private static final int LENGTH = 10;
    public static void main(String[] args) {
        // 生成数据
        int[] dataArray = new int[LENGTH];
        for (int index = 0; index < dataArray.length; index++) {
            dataArray[index] = (int) (Math.random() * LENGTH);
        }

//        int[] dataArray = {7, 3, 10, 12, 5, 1, 9, 2};
        // 打印数据
        System.out.println(Arrays.toString(dataArray));
        BinarySortTree binarySortTree = new BinarySortTree();

        long startTime = System.currentTimeMillis();
        for (int data : dataArray) {
            binarySortTree.add(new Node(data));
        }
        System.out.println("----------------消耗时间: " + (System.currentTimeMillis() - startTime) + " ms------------");

        // 打印数据
        binarySortTree.infixOrder();
        System.out.println("-----------");
        binarySortTree.delete(dataArray[0]);
        binarySortTree.infixOrder();
    }
}

class BinarySortTree {
    private Node root;

    public BinarySortTree(Node root) {
        this.root = root;
    }

    public BinarySortTree() {
        this(null);
    }

    public void add(Node node) {
        if (root == null) {
            root = node;
            return;
        }
        root.add(node);
    }

    public void infixOrder() {
        if (root == null) {
            return;
        }
        root.infixOrder();
    }

    /**
     * 根据值删除node节点
     * @param value
     * @return
     */
    public boolean delete(int value) {
        // 判断root
        if (root == null) {
            return false;
        }

        // 获取node
        Node targetNode = findNodeByData(value);
        if (targetNode == null) {
            return false;
        }
        System.out.println("targetNode --> " + targetNode);
        // 获取node的parentNode null表示targetNode为root
        Node targetParent = findParentNode(root, targetNode);
        System.out.println("targetParent --> " + targetParent);
        // 进行删除操作
        // 1.节点为叶子节点
        if (targetNode.getLeft() == null &&
            targetNode.getRight() == null) {
            // 1.1 为root节点
            if (targetParent == null) {
                root = null;
                return true;
            }
            // 1.2 不是root
            updateParentNextNode(targetParent, targetNode, null);
        }
        // 2.节点的左右都有值
        if (targetNode.getLeft() != null &&
            targetNode.getRight() != null) {
            // TODO: 2020/12/13
            if (targetNode.getRight().getLeft() == null) {
                targetNode.setDate(targetNode.getRight().getDate());
                targetNode.setRight(targetNode.getRight().getRight());
            } else {
                int data = deleteMinNode(targetNode.getRight());
                System.out.println("data --> " + data);
                targetNode.setDate(data);
            }
            return true;
        }

        // 3.节点只有一边有值,则直接子节点上升
        // 3.1 节点为root  则 直接把root指向子节点
        Node retNode = targetNode.getLeft() == null ? targetNode.getRight() : targetNode.getLeft();
        if (targetParent == null) {
            root = retNode;
            return true;
        }
        // 3.2 节点不为root
        updateParentNextNode(targetParent, targetNode, retNode);
        return true;
    }

    // 删除某个节点下最小的node 并返回最小节点的值 这里默认第一次 getLeft ！= null
    public int deleteMinNode(Node node) {
        while (node.getLeft().getLeft() != null) {
            node = node.getLeft();
        }
        int ret = node.getLeft().getDate();
        node.setLeft(null);

        return ret;
    }

    public void updateParentNextNode(Node parentNode, Node targetNode, Node newNode) {
        if (parentNode != null && targetNode != null) {
            if (parentNode.getLeft() != null &&
                    parentNode.getLeft().getDate() == targetNode.getDate()) {
                parentNode.setLeft(newNode);
            }
            if (parentNode.getRight() != null &&
                    parentNode.getRight().getDate() == targetNode.getDate()) {
                parentNode.setRight(newNode);
            }
        }
    }

    public Node findParentNode(Node node, Node targetNode) {
        if (node.getLeft() != null && node.getLeft().getDate() == targetNode.getDate()) {
            return node;
        }
        if (node.getRight() != null && node.getRight().getDate() == targetNode.getDate()) {
            return node;
        }
        if (node.getLeft() != null && node.getDate() > targetNode.getDate()) {
            return findParentNode(node.getLeft(), targetNode);
        }
        if (node.getRight() != null && node.getDate() < targetNode.getDate()) {
            return findParentNode(node.getRight(), targetNode);
        }
        return null;
    }

    public Node findNodeByData(int value) {
        if (root == null) {
            return null;
        }
        return findNodeByData(root, value);
    }

    /**
     * 根据data查找Node
     * @param node
     * @param value
     * @return
     */
    public Node findNodeByData(Node node, int value) {
        //  > value left != null
        if (node.getDate() > value && node.getLeft() != null) {
            return findNodeByData(node.getLeft(), value);
        }
        // == value
        if (node.getDate() == value) {
            return node;
        }
        // < value && right != null
        if (node.getDate() < value && node.getRight() != null) {
            return findNodeByData(node.getRight(), value);
        }
        return null;
    }

}

class Node {
    private int date;
    private Node left;
    private Node right;

    public Node(int date) {
        this.date = date;
    }

    public void add(Node node) {
        if (this.getDate() > node.getDate()) {
            if (this.getLeft() == null) {
                this.setLeft(node);
            } else {
                this.getLeft().add(node);
            }
        } else {
            if (this.getRight() == null) {
                this.setRight(node);
            } else {
                this.getRight().add(node);
            }
        }
    }

    public void infixOrder() {
        if (this.getLeft() != null) {
            this.getLeft().infixOrder();
        }
        System.out.println(this);
        if (this.getRight() != null) {
            this.getRight().infixOrder();
        }
    }


    public int getDate() {
        return date;
    }

    public void setDate(int date) {
        this.date = date;
    }

    public Node getLeft() {
        return left;
    }

    public void setLeft(Node left) {
        this.left = left;
    }

    public Node getRight() {
        return right;
    }

    public void setRight(Node right) {
        this.right = right;
    }

    @Override
    public String toString() {
        return "Node{" +
                "date=" + date +
                '}';
    }
}
